package leetcode.Hot100;

import leetcode.ListNode;

import java.util.Stack;

/**
 * @author Cheng Jun
 * Description: 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * @version 1.0
 * @date 2021/11/17 22:15
 */
public class reverseList {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2, listNode1);
        ListNode listNode3 = new ListNode(3, listNode2);
        ListNode listNode4 = new ListNode(4, listNode3);
        ListNode listNode = reverseList1(listNode4);
        System.out.println("");
    }

    // 迭代
    static ListNode reverseList(ListNode head) {
        ListNode reverse = null;
        while (head != null) {
            ListNode temp = new ListNode(head.val);
            temp.next = reverse;
            reverse = temp;
            head = head.next;
        }
        return reverse;
    }

    // 递归
    static ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;
        // 注意：此处一直返回的是尾结点，尾结点不参与下面的运算，一直返回尾结点的目的是 在递归过程中不丢失尾结点的指针
        ListNode tail = reverseList1(head.next);
        // 当前节点的 next节点的 next 指向当前节点。
        head.next.next = head;
        // 当前节点 的next 指向 null ，不然就成环了。
        head.next = null;
        return tail;
    }

    // 迭代升级版 推荐！！！
    static ListNode reverseList2(ListNode head) {
        ListNode ans = null;
        // for (ListNode i = head; i != null; i = i.next) {
        //     ans = new ListNode(i.val, ans);
        // }
        while(head != null){
            ans = new ListNode(head.val, ans);
            head = head.next;
        }
        return ans;
    }

    // stack 实现
    static ListNode reverseList3(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            ListNode temp = head.next;
            head.next = null;
            stack.push(head);
            head = temp;
        }
        // 哑节点
        ListNode listNode = new ListNode(-1);
        ListNode pointer = listNode;
        while (!stack.isEmpty()) {
            pointer.next = stack.peek();
            pointer = stack.pop();
        }
        return listNode.next;
    }
}
